package from_0_to_50;
/**
 给你一个非负整数数组nums ，你最初位于数组的第一个位置。
 数组中的每个元素代表你在该位置可以跳跃的最大长度。
 你的目标是使用最少的跳跃次数到达数组的最后一个位置。
 假设你总是可以到达数组的最后一个位置。

 示例 1:
 输入: nums = [2,3,1,1,4]
 输出: 2
 解释: 跳到最后一个位置的最小跳跃数是 2。从下标为 0 跳到下标为 1 的位置，跳1步，然后跳3步到达数组的最后一个位置。
 */
public class Q045 {
//    static int[] nums = {2,3,1,1,4};
//    static int[] nums = {2,3,0,1,4};
    static int[] nums = {0};
    static int steps = 0;
    static int minSteps = 1000000000;
    public static void main(String[] args) {
//        int[] nums = {2,3,1,1,4};
        // 13 个 2
        int[] nums = {8,2,4,4,4,9,5,2,5,8,8,0,8,6,9,1,1,6,3,5,1,2,6,6,0,4,8,6,0,3,2,8,7,6,5,1,7,0,3,4,8,3,5,9,0,4,0,1,0,5,9,2,0,7,0,2,1,0,8,2,5,1,2,3,9,7,4,7,0,0,1,8,5,6,7,5,1,9,9,3,5,0,7,5};
        int[] dp = new int[nums.length];
        new Q045().jump(nums,dp);
        System.out.println(minSteps);
    }
    public int jump(int[] nums,int[] dp) {
        dfs(nums.length-1,nums,dp);
        for (int i = nums.length-2; i >=0 ; i--) {
            minSteps = 1000000000;
            if(nums[i] == 0){
                continue;
            }
            dp[i] = getMinSteps(i,nums);
        }
        int a = 10000000;
        for (int i = 1; i <= nums[0]; i++) {
            if(a > nums[i])
                a = nums[i];
        }
        return a+1;
    }
    public static void dfs(int n,int[] nums,int[] dp){
        if(n == nums.length-1){     // 重复取值的个数
            if(steps < minSteps) {
                minSteps = steps;
            }
            return;
        }
        if(nums[n] == 0)
            return;
        for (int i = n+1; i <= n + nums[n]; i++) { // 元素个数
            if(i > nums.length-1)
                break;
            else {
                steps++;
                if(steps > minSteps){
                    steps--;
                    continue;
                }
                dfs(i,nums,dp);
                steps--;
            }
        }
    }

    public static int getMinSteps(int s,int[] nums) {
        int a = 10000000;
        if(nums[s] == 0)
            return 0;
        for (int i = s; i <= s + nums[0]; i++) {
            if(i > nums.length-1)
                break;
            if(a > nums[i])
                a = nums[i];
        }
        return a+1;
    }
}
